<!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>catalan数(卡特兰数)</title>
        <style>
</style>
        
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
<style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', system-ui, 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        <style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
        
        
        
    </head>
    <body class="vscode-light">
        <h1 id="catalan数卡特兰数">catalan数(卡特兰数)</h1>
<h1 id="1-推导公式">1. 推导公式</h1>
<p>卡特兰数的递推公式是</p>
<pre><code>F(n)=∑(k=1…n){F(k-1)*F(n-k)}=∑(k=0…n-1){F(k)*F(n-k-1)} 有点类似于卷积
</code></pre>
<p>一般性公式为</p>
<pre><code>F(n)=C(2n,n) - C(2n,n+1) 
F(n)=C(2n,n)/(n+1)
F(n)=F(n-1)*(4*n-2)/(n+1)
</code></pre>
<h1 id="2-可以描述的问题">2. 可以描述的问题</h1>
<ul>
<li>n个元素的二叉查找树有多少种。</li>
<li>矩阵链所有乘法顺序问题</li>
<li>凸多边形剖分成三角形的方法数</li>
<li>前序遍历二叉树序列能对应多少个二叉树
<ul>
<li><a href="https://www.youtube.com/watch?v=RUB5ZPfKcnY&amp;list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr&amp;index=42">https://www.youtube.com/watch?v=RUB5ZPfKcnY&amp;list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr&amp;index=42</a></li>
</ul>
</li>
<li>n*n棋盘从左下角走到右上角而不穿过主对角线的走法。</li>
<li>2n个人排队买票问题，票价50，n个人拿50元，n个人拿100元，售票处无零钱，能顺利卖票的所有排队方式。</li>
<li>n个元素全部入栈并且全部出栈的所有可能顺序。</li>
<li>括号合法匹配问题</li>
</ul>
<h1 id="3-n个元素的二叉查找树有多少种">3. n个元素的二叉查找树有多少种。</h1>
<h2 id="31-问题的解是fn-k1nfk-1fn-k--k0n-1fkfn-1-k">3.1 问题的解是F(n)= ∑(k=1…n){F(k-1)*F(n-k)} = ∑(k=0…n-1){F(k)*F(n-1-k)}</h2>
<p>因为一棵n个结点的二叉排序树的根可以是1到n的任意结点，设为k，则其左子树结点个数为k，左子树的种类一共有F(k-1)种，右子树结点个数为n-k，右子树的种类一共有F(n-k)。而究竟哪一点为根可以有1到n共n个选择，故k取遍1到n</p>
<pre><code><code><div>F(0) = 1
F(1) = 1
F(2) = F(0) * F(1) + F(1) * F(0) = 2
F(3) = F(0) * F(2) + F(1) * F(1) + F(2) * F(0) = 5
 

F(n)=∑(k=1…n){F(k-1)*F(n-k)}。 还可以参考96. Unique Binary Search Trees
</div></code></code></pre>
<p>思考： 有没有办法能直接推导出 F(n) = C(2n,n) - C(2n, n+1)   ?  等价为括号匹配问题?  不太容易， 下面的括号匹配，找零钱等问题， 都是2n个元素(操作).  而 二叉树，矩阵链等问题都是n个元素.</p>
<p>如何生成所有的二叉查找树  95. Unique Binary Search Trees II</p>
<h2 id="32-类似的问题">3.2 类似的问题</h2>
<ul>
<li>矩阵链所有乘法顺序问题</li>
<li>凸多边形剖分成三角形的方法数</li>
<li>圆桌握手问题： 圆桌周围有 2n个人，他们两两握手，但没有交叉的方案数</li>
</ul>
<h2 id="33-矩阵链所有乘法顺序问题">3.3 矩阵链所有乘法顺序问题</h2>
<pre><code><code><div>M1 * M2 * M3 * M4 * M5 * … Mn

类似于n个元素的二叉查找树的种类个数。 
以M1 为根节点的数目是， F(0) * F(n-1)
以M2 为根节点的数目是， F(1) * F(n-2)
…
以Mn 为根节点的数目是， F(n-1) * F(0)

F(n) = ∑(k=1…n){F(k-1)*F(n-k)}

F(1) = 1
F(2) = F(1) * F(1) = 1
F(3) = F(1) * F(2) + F(2) * F(1) = 2
F(4) = F(1) * F(3) + F(2) * F(2) + F(3) * F(1) = 5
</div></code></code></pre>
<h2 id="34-凸多边形剖分成三角形的方法数">3.4 凸多边形剖分成三角形的方法数</h2>
<p>给定一个n多边形，要求用n-3条不相交的对角线把它分成n-2个三角形。求有多少种不同的方法。</p>
<p>为什么是n-3条不相交的对角线？</p>
<p>n多边形有n个顶点，依次将其编号为V1、V2、V3、…、Vn。
从V1号到V3号连线，分成一个三角形和一个（n-2)边形（因为顶点有n-3+1个）。再对（n-2)边形重新编号，并从V1号到V3号连线，如此重复，连n-3次就可以n-2个三角形。
也就是说用不相交的对角线来分割多边形为三角形，一定是n-3条线和n-2个三角形。</p>
<p>对于边V1Vn,任选一顶点Vk，向V1和Vn连边。将三角形V1VnVk分割出去，剩下两个多边形，一个多边形有顶点{1，2，3，…，k}，所以是k边形；另一个多边形有顶点{k，k+1,…,n}，所以是（n-k+1）边形。然后继续分割多边形直到都变成了三角形，这个过程可以用递归或递推实现。</p>
<p>回顾下我们分割的过程：先选边V1Vn，因为编号是我们遍的，所以不管我们选哪条边，都可以看成V1Vn。选边V1Vn只有一种可能。然后选顶点Vk，Vk的取值范围为[V2，Vn-1],选顶点有n-2种可能。再递归调用d(k)和d(n-k+1)去计算。
综上，枚举k从2到n-1，累加d(k)*d(n-k+1)的值即可。</p>
<p>设d(n)表示将n边形分割成三角形的方法数。</p>
<p>递推版：</p>
<pre><code><code><div>由下及上，边界
d[0]=1
d[1]=1
d[2]=1
d[3]=1
d[4]=d[2] * d[3] + d[3] * d[2] = 2
d[5]=d[2] * d[4] + d[3] * d[3] + d[4] * d[2] = 5
d[6]=d[2] * d[5] + d[3] * d[4] + d[4] * d[3] + d[5] * d[2] = 14 
…
d[n]=d[2]*d[n-1]+d[3]*d[n-2]+…+d[n-2]*d[2].
</div></code></code></pre>
<p><img src="file:///e:\gitee\leetcode\math\pics\catalan1.png" alt="catalan1.png"></p>
<p>上图是n=6的情况。 以v1~v6为基础边， 分别从v2	~ v5 中间选择一个点， 构成三角形。将六边形分为两块。
如果选择v2(pic1)，三角形 v1~v2~v6 将六边形分为两块。 v1~v2 构成的线条d(2)=1, v2~v3~v4~v5~v6 构成的五边形 d(5),     这种情况下的种类数就是 d(2) * d(5) = 5</p>
<p>d[6]=d[2] * d[5] + d[3] * d[4] + d[4] * d[3] + d[5] * d[2] = 14</p>
<p>￼</p>
<h1 id="4-nn棋盘从左下角走到右上角而不穿过主对角线的走法">4. n*n棋盘从左下角走到右上角而不穿过主对角线的走法。</h1>
<h2 id="解法1fnk1nfk-1fn-kk0n-1fk-1fn-k">解法1：F(n)=∑(k=1…n){F(k-1)*F(n-k)}=∑(k=0…n-1){F(k-1)*F(n-k)}</h2>
<p>考虑n<em>n棋盘，记主对角线为L。从左下角走到右上角不穿过对角线L的所有路径，不算起点，一定有第一次接触到L的位置（可能是终点），设此位置为M，坐标为(x,x)——设第一个数为横轴坐标。该路径一定从下方的(x,x-1)而来，而起点处第一步也一定是走向(1,0)，两者理由相同——否则就穿过了主对角线。
考虑从(1,0)到(x,x-1)的(x-1)</em>(x-1)的小棋盘中，因为在此中路径一直没有接触过主对角线（M的选取），所以在此小棋盘中路径也一定没有穿过从(1,0)到(x,x-1)的小棋盘的对角线L1。这样在这个区域中的满足条件的路径数量就是一个同构的子问题，解应该是F(x-1)，
而从M到右上角终点的路径数量也是一个同构的子问题，解应该是F(n-x)，</p>
<p>第一次接触到主对角线点为(x,x) 情况下 的可能走法有 F(x-1) * F(n-x)</p>
<p>而第一次接触到主对角线的点可以从(1,1)取到(n,n)，这样就有
F(n)= F(1-1) * F( n-1) + F(2-1) * F(n-2) + … F(n-1) * F(0)
= ∑(k=1…n){F(k-1)*F(n-k)}
= ∑(k=0…n-1){F(k)*F(n-k-1)}。
￼
￼<img src="file:///e:\gitee\leetcode\math\pics\catalan2.png" alt="catalan2.png">
￼</p>
<p>￼</p>
<h2 id="解法2-fnc2nn---c2nn1--c2nnn1">解法2： F(n)=C(2n,n) - C(2n,n+1) = C(2n,n)/(n+1)</h2>
<p>思路是先求所有从(0,0)到(n,n)的路径数X，再求所有穿过主对角线L的从(0,0)到(n,n)的路径数Y，用前者减去后者得到所求。
先求X:
从(0,0)到(n,n)的路径数显然是C(2n,n)，一共要走2n步到达右上角，其中向右和向上各n步，总走法是X = C(2n,n)。</p>
<p>再求Y:
考虑一个新增的位置(n-1,n+1)，它位于终点的左上角一个格处，设所有从(0,0)到(n-1,n+1)的路径数为Z，下面要证明Y和Z相等，从而通过求Z来求Y。
考虑从(0,1)到(n-1,n)的对角线L2，对于所有穿过L而到达终点的路径，一定会接触到L2，找出某路径第一次接触到L2的位置M1，将从M1到终点的路径沿L2做对折一定会得到一条从M1到(n-1,n+1)的路径，故每条穿过L到达终点的路径都对应一条到达(n-1,n+1)的路径，即有Y&lt;=Z。</p>
<p>所有从起点到达(n-1,n+1)的路径都一定会穿过L2，找出某路径第一次穿过L2的位置M2，将M2到(n-1,n+1)的路径沿L2对折，就得到一条M2到(n,n)的路径，且该条路径一定穿过L，故每条到达(n-1,n+1)的路径都对应一条穿过L到达终点的路径，即有Z&lt;=Y。</p>
<p>故Z==Y。</p>
<p>￼<img src="file:///e:\gitee\leetcode\math\pics\catalan3.png" alt="catalan3.png"></p>
<p>接下来通过求Z来求Y。Z是显然的从(0,0)到(n-1,n+1)共需走2n步，其中向右n-1步、向上n+1步，故Z=C(2n,n-1)。
由以上可知F(n)=X-Y=X-Z=C(2n,n)-C(2n,n-1)=C(2n,n)/(n+1)。证毕。</p>
<p>￼</p>
<h2 id="41-类似的问题">4.1 类似的问题</h2>
<ul>
<li>2n个人排队买票问题，票价50，n个人拿50元，n个人拿100元，售票处无零钱，能顺利卖票的所有排队方式。</li>
<li>n个元素全部入栈并且全部出栈的所有可能顺序。</li>
<li>括号合法匹配问题</li>
</ul>
<p>都可以抽象成2n个操作组成的操作链，其中A操作和B操作各n个，且要求截断到操作链的任何位置都有：
A操作（向右走一步、收到50元、元素入栈, 遇到一个左括号 ）的个数不少于B操作（向上走一步、收到100元找出50元、元素出栈, 遇到一个右括号 ）的个数。</p>
<h2 id="42-括号匹配问题">4.2 括号匹配问题</h2>
<h3 id="解法1-fnk1nfk-1fn-kk0n-1fk-1fn-k">解法1:   F(n)=∑(k=1…n){F(k-1)*F(n-k)}=∑(k=0…n-1){F(k-1)*F(n-k)}</h3>
<p>及 F(n) 表示 n个左括号和n个右括号组成的所有合法组合数目
类似于前面的走格子问题。 括号字符串长度 2n,  假设在第2x位置上，第一次出现了左括号和右括号数目相等的情况， 即1~2x 字符串里面有 x个左括号， x个右括号.    这就可以拆分成2 部分</p>
<ul>
<li>1~2x 字符串 的第一个元素一定是左括号， 第2x个元素一定是右括号.     在2 ~ (2x-1) 里面， 有(x-1)个左括号， (x-1)个右括号， 合法情况有  F(x-1) 种。</li>
<li>2x+1 ~ 2n  字符串里面有 有(n-x)个左括号， (n-x)个右括号， 合法情况有  F(n-x) 种。</li>
</ul>
<p>合法数目就是 F(x-1) * F(n-x)</p>
<p>总的合法数目就是  F(n)=∑(k=1…n){F(k-1)*F(n-k)}</p>
<h3 id="解法2-fnc2nn---c2nn1--c2nnn1-1">解法2: F(n)=C(2n,n) - C(2n,n+1) = C(2n,n)/(n+1)</h3>
<ul>
<li>设所有的组合数目(不管合不合法)是X, 则 X = C(2n,n)  相等于在2n个位置里面，选择n个位置放左括号， 剩下的n个位置放右括号</li>
<li>设所有的非法数目为Y, 则 Y = C(2n,n+1)</li>
</ul>
<p>我们可以证明所有的非法数目Y1，等于 n+1个右括号 和 n-1个左括号组成的所有组合数目Y2。   Y1 == Y2</p>
<ol>
<li>假设有n个左括号和n个右括号组成的非法组合， 在字符串1~x上第一次出现了 右括号数目大于左括号数目， 那么在 x+1 ~ 2n 的字符串里面我们做一个翻转，将左括号变为右括号，右括号变为左括号， 最后得到的字符串里面就有  n+1个右括号 和 n-1个左括号, 即  Y1 &lt;= Y2</li>
<li>n+1个右括号 和 n-1个左括号组成的字符串里面， 一定存在x, 在字符串1~x上第一次出现了 右括号数目大于左括号数目,  那么在 x+1 ~ 2n 的字符串里面我们做一个翻转，将左括号变为右括号，右括号变为左括号， 最后得到的字符串里面就有  n个右括号 和 n个左括号, 即  Y2 &lt;= Y1</li>
</ol>
<pre><code><code><div>最终Y1 == Y2.
Y2的数目很容易求出  C(2n,n+1)
最后合法的结果就是 X- Y = C(2n,n) - C(2n,n+1)
</div></code></code></pre>
<h2 id="43-如果要打印出所有的合法匹配的括号方案">4.3 如果要打印出所有的合法匹配的括号方案？</h2>
<p>LC 22. Generate Parentheses</p>
<pre><code><code><div># 合法括号匹配数目，假设n个左括号， n个右括号。 有多少种合法的括号排列组合。  
from pprint import pprint
def generate_helper(mlist, current, left_num, right_num):
    if left_num == 0 and right_num == 0:
        pprint(mlist)
        return
    if left_num &gt; 0:
        mlist[current] = &quot;(&quot;
        generate_helper(mlist, current+1, left_num-1, right_num)
    if right_num &gt; left_num:
        mlist[current] = &quot;)&quot;
        generate_helper(mlist, current+1, left_num, right_num-1)

def generate(n):
    print(f&quot;======= {n} =======&quot;)
    mlist = [&quot;0&quot;] * 2 * n
    generate_helper(mlist, 0, n, n)
generate(1)  
generate(2) 
generate(3)
Generate(4)

======= 1 =======
['(', ')']
======= 2 =======
['(', '(', ')', ')']
['(', ')', '(', ')']
======= 3 =======
['(', '(', '(', ')', ')', ')']
['(', '(', ')', '(', ')', ')']
['(', '(', ')', ')', '(', ')']
['(', ')', '(', '(', ')', ')']
['(', ')', '(', ')', '(', ')']
======= 4 =======
['(', '(', '(', '(', ')', ')', ')', ')']
['(', '(', '(', ')', '(', ')', ')', ')']
['(', '(', '(', ')', ')', '(', ')', ')']
['(', '(', '(', ')', ')', ')', '(', ')']
['(', '(', ')', '(', '(', ')', ')', ')']
['(', '(', ')', '(', ')', '(', ')', ')']
['(', '(', ')', '(', ')', ')', '(', ')']
['(', '(', ')', ')', '(', '(', ')', ')']
['(', '(', ')', ')', '(', ')', '(', ')']
['(', ')', '(', '(', '(', ')', ')', ')']
['(', ')', '(', '(', ')', '(', ')', ')']
['(', ')', '(', '(', ')', ')', '(', ')']
['(', ')', '(', ')', '(', '(', ')', ')']
['(', ')', '(', ')', '(', ')', '(', ')']
</div></code></code></pre>

    </body>
    </html>